package primaryAlgorithm.countPrimes;
/**
 * @Date 2020/03/25
 * @author 18795
 * @Thinking 更改思路，将所有不是质数的数找出来
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（n）
 */
public class MyMethodThree {
	public int countPrimes(int n) {
		boolean[] judge=new boolean[n+1]; //true代表：不是质数，false代表质数
		//将2-n范围内的非质数下标全部置为true
		for(int i=2;i<n;i++) {
			if(!judge[i]) {
				for(int j=2*i;j<n;j+=i)
					judge[j]=true;
			}
		}
		//统计所有false的个数，false次数就是2-n范围中质数的个数
		int count=0;
		for(int i=2;i<=n;i++)
			if(!judge[i])count++;
		return count;
	}
}
